package interview;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class interview_08_02 {
    public List<List<Integer>> pathWithObstacles(int[][] obstacleGrid) {
        int m=obstacleGrid.length;
        int n=obstacleGrid[0].length;
        List<List<Integer>> path=new LinkedList();
        List<List<List<Integer>>> result = new ArrayList<>();
        boolean[][] used=new boolean[m][n];
        boolean[] flag=new boolean[1];
        search(result,path,m,n,obstacleGrid,0,0,flag,used);
        if(result.size()==0) return new ArrayList<>();
        return result.get(0);
    }
    public void search(List<List<List<Integer>>> result,List<List<Integer>> path,int m,int n,int[][] obstacleGrid,int i,int j,boolean[] flag,boolean[][] used){
        if(flag[0]) return;
        if(i>=0&&i<m&&j>=0&&j<n&&used[i][j]==false){
            if(obstacleGrid[i][j]==1) return;
            List<Integer> tmp=new ArrayList<>();
            tmp.add(i);
            tmp.add(j);
            used[i][j]=true;
            path.add(tmp);
            if(i==m-1&&j==n-1){
                result.add(new ArrayList<>(path));
                flag[0]=true;
                return;
            }
            search(result, path, m, n, obstacleGrid, i+1, j,flag,used);
            search(result, path, m, n, obstacleGrid, i, j+1,flag,used);
            path.remove(path.size()-1);
        }
    }
}
